struct Solution {}

impl Solution {
  pub fn best_rotation(nums: Vec<i32>) -> i32 {
  let n = nums.len();
  let mut cnt = vec![0; n];
  nums.iter().enumerate().for_each(|(i, v)| {
    let l = (i + 1) % n;
    let h = (i - *v as usize + n + 1) % n;
    cnt[l] += 1;
    cnt[h] -= 1;
    if l >= h {
      cnt[0] += 1;
    } 
  });
  let mut best = 0;
  let mut ret = 0;
  let mut curr = 0;
  for i in 0..n {
    curr += cnt[i];
    if curr > best {
      best = curr;
      ret = i;
    }
  }
  ret as i32
  }
} 

// 未用差分数组 超时 思路对
// impl Solution {
//   pub fn best_rotation(nums: Vec<i32>) -> i32 {
//   let l = nums.len();
//   let mut cnt = vec![0; l + 1];
//   nums.iter().enumerate().for_each(|(i, v)| {
//     let t = i as i32 - v;
//     if t < 0 {
//       let r = l - i;
//       if (-t as usize) < r {
//         for e in -t as usize..l - i{
//           cnt[e] += 1;
//         }
//       }
//     }
//     else {
//       let mut r = 0;
//       if t as usize >= i {
//         r = l;
//       } else {
//         r = l - i;
//         for e in l - t as usize ..l {
//           cnt[e] += 1;
//         }
//       }
//       for e in 0..r {
//         cnt[e] += 1;
//       }
//     }
//   });
//   cnt[l] += cnt[0];
//   cnt[0] = -1;
//   let (v, t) = cnt.iter().enumerate().reduce(|(i1, v1), (i2, v2)| {
//     if v1 > v2 {
//       (i1, v1)
//     } else {
//       (i2, v2)
//     }
//   }).unwrap();
//   (l - v) as i32 
//   }
// } 